1. Field of the Invention
This invention relates to a computer data storage system, and more particularly to a redundant data storage array system in which a plurality of storage units are divided into logical arrays such that redundant array controllers may concurrently access stored data.
2. Description of Related Art
A typical data processing system generally includes one or more storage units which are connected to a Central Processing Unit (CPU) either directly or through a control unit and a channel. The function of the storage units is to store data and programs which the CPU uses in performing particular data processing tasks.
Various types of storage units are used in current data processing systems. A typical system may include one or more large capacity tape units and/or disk drives (magnetic, optical, or semiconductor) connected to the system through respective control units for storing data. A research group at the University of California, Berkeley, in a paper entitled "A Case for Redundant Arrays of Inexpensive Disks (RAID)", Patterson, et al., Proc. ACM SIGMOD, June 1988, has catalogued a number of different approaches for providing such reliability when using disk drives as failure independent storage units. Arrays of disk drives are characterized in one of five architectures, under the acronym "RAID" (for Redundant Arrays of Inexpensive Disks).
A RAID 1 architecture involves providing a duplicate set of "mirror" storage units and keeping a duplicate copy of all data on each pair of storage units. While such a solution solves the reliability problem, it doubles the cost of storage. A number of implementations of RAID 1 architectures have been made, in particular by Tandem Corporation.
A RAID 2 architecture stores each bit of each word of data, plus Error Detection and Correction (EDC) bits for each word, on separate disk drives. For example, U.S. Pat. No. 4,722,085 to Flora et al. discloses a disk drive memory using a plurality of relatively small, independently operating disk subsystems to function as a large, high capacity disk drive having an unusually high fault tolerance and a very high data transfer bandwidth. A data organizer adds 7 EDC bits (determined using the well-known Hamming code) to each 32-bit data word to provide error detection and error correction capability. The resultant 39-bit word is Written, one bit per disk drive, on to 39 disk drives. If one of the 39 disk drives fails, the remaining 38 bits of each stored 39-bit word can be used to reconstruct each 32-bit data word on a word-by-word basis as each data word is read from the disk drives, thereby obtaining fault tolerance.
An obvious drawback of such a system is the large number of disk drives required for a minimum system (since most large computers use a 32-bit word), and the relatively high ratio of drives required to store the EDC bits (7 drives out of 39). A further limitation of a RAID 2 disk drive memory system is that the individual disk actuators are operated in unison to write each data block, the bits of which are distributed over all of the disk drives. This arrangement has a high data transfer bandwidth, since each individual disk transfers part of a block of data, the net effect being that the entire block is available to the computer system much faster than if a single drive were accessing the block. This is advantageous for large data blocks. However, this arrangement effectively provides only a single read/write head actuator for the entire storage unit. This adversely affects the random access performance of the drive array when data files are small, since only one data file at a time can be accessed by the "single" actuator. Thus, RAID 2 systems are generally not considered to be suitable for computer systems designed for On-Line Transaction Processing (OLTP), such as in banking, financial, and reservation systems, where a large number of random accesses to many small data files comprises the bulk of data storage and transfer operations.
A RAID 3 architecture is based on the concept that each disk drive storage unit has internal means for detecting a fault or data error. Therefore, it is not necessary to store extra information to detect the location of an error; a simpler form of parity-based error correction can thus be used. In this approach, the contents of all storage units subject to failure are "Exclusive OR'd" (XOR'd) to generate parity information. The resulting parity information is stored in a single redundant storage unit. If a storage unit fails, the data on that unit can be reconstructed onto a replacement storage unit by XOR'ing the data from the remaining storage units with the parity information. Such an arrangement has the advantage over the mirrored disk RAID 1 architecture in that only one additional storage unit is required for "N" storage units. A further aspect of the RAID 3 architecture is that the disk drives are operated in a coupled manner, similar to a RAID 2 system, and a single disk drive is designated as the parity unit.
One implementation of a RAID 3 architecture is the Micropolis Corporation Parallel Drive Array, Model 1804 SCSI, that uses four parallel, synchronized disk drives and one redundant parity drive. The failure of one of the four data disk drives can be remedied by the use of the parity bits stored on the parity disk drive. Another example of a RAID 3 system is described in U.S. Pat. No. 4,092,732 to Ouchi.
A RAID 3 disk drive memory system has a much lower ratio of redundancy units to data units than a RAID 2 system. However, a RAID 3 system has the same performance limitation as a RAID 2 system, in that the individual disk actuators are coupled, operating in unison. This adversely affects the random access performance of the drive array when data files are small, since only one data file at a time can be accessed by the "single" actuator. Thus, RAID 3 systems are generally not considered to be suitable for computer systems designed for OLTP purposes.
A RAID 4 architecture uses the same parity error correction concept of the RAID 3 architecture, but improves on the performance of a RAID 3 system with respect to random reading of small files by "uncoupling" the operation of the individual disk drive actuators, and reading and writing a larger minimum amount of data (typically, a disk sector) to each disk (this is also known as block striping). A further aspect of the RAID 4 architecture is that a single storage unit is designated as the parity unit.
A limitation of a RAID 4 system is that Writing a data block on any of the independently operating storage units also requires writing a new parity block on the parity unit. The parity information stored on the parity unit must be read and XOR'd with the old data (to "remove" the information content of the old data), and the resulting sum must then be XOR'd with the new data (to provide new parity information). Both the data and the parity records then must be rewritten to the disk drives. This process is commonly referred to as a "Read-Modify-Write" (RMW) operation.
Thus, a Read and a Write on the single parity unit occurs each time a record is changed on any of the storage units covered by a parity record on the parity unit. The parity unit becomes a bottle-neck to data writing operations since the number of changes to records which can be made per unit of time is a function of the access rate of the parity unit, as opposed to the faster access rate provided by parallel operation of the multiple storage units. Because of this limitation, a RAID 4 system is generally not considered to be suitable for computer systems designed for OLTP purposes. Indeed, it appears that a RAID 4 system has not been implemented for any commercial purpose.
A RAID 5 architecture uses the same parity error correction concept of the RAID 4 architecture and independent actuators, but improves on the writing performance of a RAID 4 system by distributing the data and parity information across all of the available disk drives. Typically, "N+1" storage units in a set (also known as a "redundancy group") are divided into a plurality of equally sized address areas referred to as blocks. Each storage unit generally contains the same number of blocks. Blocks from each storage unit in a redundancy group having the same unit address ranges are referred to as "stripes". Each stripe has N blocks of data, plus one parity block on one storage device containing parity for the N data blocks of the stripe. Further stripes each have a parity block, the parity blocks being distributed on different storage units. Parity updating activity associated with every modification of data in a redundancy group is therefore distributed over the different storage units. No single unit is burdened with all of the parity update activity.
For example, in a RAID 5 system comprising 5 disk drives, the parity information for the first stripe of blocks may be Written to the fifth drive; the parity information for the second stripe of blocks may be Written to the fourth drive; the parity information for the third stripe of blocks may be Written to the third drive; etc. The parity block for succeeding stripes typically "processes" around the disk drives in a helical pattern (although other patterns may be used).
In systems such as the RAID systems described above, in which an array of storage units is controlled by an array control unit (controller), a problem exists if the controller fails, thereby making information contained in the storage units coupled to that controller unavailable to the system. Often, such a failure will shut down the entire computer system.
The prior art has suggested ways to solve the problem of reliably storing and retrieving data despite the possibility that an array controller may fail. FIG. 1 illustrates one way suggested in the prior art to resolve this problem. In the system shown in FIG. 1, redundant controllers 3, 4 are provided, such that each storage unit 40-51, arranged in two redundancy groups is coupled to a CPU 1 through the controllers 3, 4. Each controller 3, 4 is coupled to each storage unit 40-51 by a multiplicity of channels 5. Each of the channels 5 is a multi-user bus, such as a Small Computer System Interface (SCSI) bus. While twelve storage units 40-51 are shown for illustrative purposes, the broken lines between the storage units 40-51 indicate that a multiplicity of other storage units may be present in the invention. A single one of the data channels 5 couples each of the storage units in a single column (for example, 40 and 46; 41 and 47; 42 and 48, etc.) to each other and to the two controllers 3, 4.
In such systems, one controller 3 is considered to be the primary controller and the other to be a secondary controller 4. The primary controller 3 is responsible for the task of interfacing storage units 40-51 to the CPU 1. Only when there is a failure of the primary controller 3 does the secondary controller 4 become active. If the primary controller 3 fails, the secondary controller 4 assumes the full responsibility for interfacing the storage units 40-51 to the CPU 1.
FIG. 2 shows how the data storage area is allocated in a typical storage unit used in such prior art data storage systems. A diagnostics section 11 comprising one or more data blocks at each end of the addressable storage space is allocated for the purpose of determining whether the storage unit is functional. Diagnostic codes may be written into this area and subsequently read back. Following the diagnostic section 11 is a section 12 known in the art as a "reserved area" which is used to store such information as system configuration data, further diagnostics data, scratch pad, primary software, and secondary software. Following the reserved area, and comprising the majority of the data storage area of the storage unit, is the user area 14. The user area 14 comprises those blocks of data available to the system user and the system tasks.
Two problems exist in the system shown in FIG. 1. Firstly, the secondary controller 4 is not utilized under normal conditions. Therefore, the potential of the system is greater than its normal capability. Such a waste of resources is costly and inefficient.
Secondly, if the primary controller 3 fails, the secondary controller 4 may not be capable of determining that a failure has occurred and what steps must be taken to continue any operations which were in progress at the time of the failure.
One factor which limits the ability of the system to take full advantage of the secondary controller's 4 potential is the concern over "collisions" between the controllers 3, 4. A collision occurs when more than one controller attempts to write data blocks within the same redundancy group in a RAID system. When data is to be written to a storage unit of a RAID system, a RMW operation must be performed.
It is possible for redundant controllers to each begin modifying data blocks within the same redundancy group, thereby causing the redundancy group to maintain an inaccurate parity block. To illustrate this refer to FIG. 3(a)-3(c). FIG. 3(a) illustrates the values of data blocks 101-105 of a single redundancy group in a system in which five storage units 200-204 comprise a redundancy group. An array controller 106 is the primary controller and a second array controller 107 is a redundant controller. Stored in data block 101 of storage unit 200 is the value "1001." Data block 102 of storage unit 201 has the value "1110." The value "0010" is stored in data block 103 of storage unit 202. The value "1010" is stored in data block 104 of storage unit 203. A parity storage unit 204 has the value stored in data block 105, comprising the exclusive-OR sum ("1111") of the data blocks 101-104 stored in the other storage units 200-203.
If the primary array controller 106 begins a RMW operation to data block 101 of storage unit 200, the controller 106 will accept into an "old data" register 108 the value of the data block that is to be modified. Therefore, the value "1001" will be read and stored in register 108. The value of data block 105 of the parity storage unit 204 will be read and stored in an "old parity" data register 109 of the primary array controller 106. The next step in the RMW sequence is to calculate the exclusive-OR (XOR) sum of the old data and the old parity values. The XOR sum ("0110") is stored as a partial-parity value in a result register 116 in the primary array controller 106. The value of the result register 116 is then XOR summed with the value of the new data in a "new data" register 110 of the primary array controller 106. The resulting final parity value ("1100") is stored in a "new parity" register 111.
If the redundant array controller 107 were to attempt to perform a second RMW to a different data block 102 within the same redundancy group during the time the primary array controller 106 was calculating a new parity value for data block 1 01, a read of the old data block 102 and the old parity block 105 would be performed and the values of the old data block 102 and the old parity block 105 would be stored in corresponding old data and old parity registers 112, 113 in the redundant array controller 107.
The same operations that were performed in the primary controller 106 would be performed in the redundant array controller 107 and the new data and new parity values would be stored in corresponding new data register, and new parity registers 114, 115 of the redundant array controller 107. It is then possible that during the time that the new parity value is being calculated in the redundant array controller 107, the primary array controller 106 will update data block 101 of storage unit 200 and parity block 105 of parity storage unit 204, as shown in FIG. 3b.
In FIG. 3c, the values of the new data and new parity calculated in the redundant array controller 107 are stored in data block 102 of storage unit 201 and data block 105 of the parity storage unit 204. However, because the redundant array controller 107 read the old parity value from data block 105 of the parity storage unit 204 before the change made by the primary array controller 106, the value now stored in data block 105 of the parity storage unit 204 does not take into account the change made to data block 1 01 of storage unit 200. Therefore, the system will not be capable of recovering the data stored if a failure occurs. This is undesirable in a fault tolerant system.
Therefore, it is desirable to provide means which allows two or more array controllers to be simultaneously active without losing the ability to completely recover from a failure of one of the storage units, while maintaining the capability of each controller to take over the tasks of the other controller if a failure occurs. It is also desirable to provide a method by which any controller may be removed from (or brought into) service such that any other controller may begin (or cease) performing the tasks of the controller so removed from (or brought into) service. The present invention provides such means and method.